UVa/10298 - Power Strings/10298.3.cpp

   1 using namespace std;
   2 #include <algorithm>
   3 #include <iostream>
   4 #include <iterator>
   5 #include <numeric>
   6 #include <sstream>
   7 #include <fstream>
   8 #include <cassert>
   9 #include <climits>
  10 #include <cstdlib>
  11 #include <cstring>
  12 #include <string>
  13 #include <cstdio>
  14 #include <vector>
  15 #include <cmath>
  16 #include <queue>
  17 #include <deque>
  18 #include <stack>
  19 #include <list>
  20 #include <map>
  21 #include <set>
  22
  23 #define foreach(x, v) for (typeof (v).begin() x=(v).begin(); x !=(v).end(); ++x)
  24 #define For(i, a, b) for (int i=(a); i<(b); ++i)
  25 #define D(x) cout << #x " is " << x << endl
  26
  27 const int MAXN = 1000001 * 2;
  28
  29 int border[MAXN];
  30 char s[MAXN];
  31
  32 int main(){
  33     while (true) {
  34         gets(s);
  35         int n = strlen(s);
  36         if (n == 1 and s[0] == '.') break;
  37         assert(n > 0);
  38         if (n == 1) {
  39             printf("%d\n", n);
  40             continue;
  41         }
  42         for (int i = n; i < 2 * n; ++i) {
  43             s[i] = s[i - n];
  44         }
  45         s[2 * n] = '\0';
  46         assert(strlen(s) == 2 * n);
  47
  48         border[0] = 0;
  49         for (int i = 1; i < 2 * n; ++i) {
  50             int k = border[i - 1];
  51             while (k > 0 and s[i] != s[k]) k = border[k - 1];
  52             if (s[i] == s[k]) k++;
  53             border[i] = k;
  54         }
  55
  56         for (int i = n; i < 2 * n; ++i) {
  57             if (border[i] == n) {
  58                 assert(n % (i - n + 1) == 0);
  59                 printf("%d\n", n / (i - n + 1));
  60                 break;
  61             }
  62         }
  63
  64    }
  65     return 0;
  66 }